//给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
//
// 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
//
//
//
// 示例 1:
//
//
//输入: nums = [1,1,2,3,3,4,4,8,8]
//输出: 2
//
//
// 示例 2:
//
//
//输入: nums =  [3,3,7,7,10,11,11]
//输出: 10
//
//
//
//
//
//
//
// 提示:
//
//
// 1 <= nums.length <= 10⁵
// 0 <= nums[i] <= 10⁵
//
//
//
//
//
// 注意：本题与主站 540 题相同：https://leetcode-cn.com/problems/single-element-in-a-sorted-
//array/
//
// Related Topics 数组 二分查找 👍 67 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function singleNonDuplicate(nums: number[]): number {

    let low = 0, high = nums.length - 1;
    while (low < high) {
        const mid = Math.floor((high - low) / 2) + low;
        //? 在JavaScript中，将一个数与1进行异或操作会将该数的最后一位取反
        //? 这里就是如果 mid 是偶数，则比较 nums[mid] 和 nums[mid+1] 是否相等；此时mid前有偶数个 一定没有目标
        //? 如果 mid 是奇数，则比较 nums[mid−1] 和 nums[mid] 是否相等。此时mid与mid-1相等 mid -1左边个数为偶 没有目标值
        //? 当 mid 是偶数时，偶数二进制末位一定为0 mid+1 === mid^1；
        //? 当 mid 是奇数时，奇数二进制末位一定为1 mid−1 === mid^1。
        if (nums[mid] === nums[mid ^ 1]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return nums[low];
};
//leetcode submit region end(Prohibit modification and deletion)
